package com.example.algorithm.backtracing;

/**
 * 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
 *
 *  示例:
 *  输入: 2
 * 输出: 91
 * 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
 */
public class Leetcode357_CountNumbersWithUniqueDigits {
    public static void main(String[] args) {
        // 32491
        System.out.println(new Solution().countNumbersWithUniqueDigits(2));

    }

    static class Solution {
        /**
         * 动态规划
         * n > 10时，令n = 10
         * Sn为n位不同整数的值（一定是n个数字组成，第一位不能为0，且各个数字不同），
         * 如S3 = 648，
         * 结果：ans = S0 + S1 + ... + Sn
         */
        public int countNumbersWithUniqueDigits(int n) {
            if (n == 0) {
                return 1;
            }
            int[] dp = new int[n + 1]; // dp[i] = m 表示dp[i] 为位数恰好为i位的数字 每位都不相同的数字的数量
            dp[0] = 1;
            dp[1] = 9;
            int res = 10;
            int min = Math.min(10, n); // 超过10位数字的,必有重复数字,所以最大的位数为10

            for (int i = 1; i < min; i++) {
                System.out.println("xx");
                dp[i + 1] = dp[i] * (10 - i);
                res += dp[i + 1];// 所有长度对应数量累加
            }

            return res;

        }
    }
}
